// Created by WXX on 2022/1/24 17:02
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

/**
 * 执行用时：660 ms, 在所有 C++ 提交中击败了39.61%的用户
 * 内存消耗：181.1 MB, 在所有 C++ 提交中击败了57.90%的用户
 */
typedef pair<int, int> PII;

#define x first
#define y second

class Solution {
public:
    vector<vector<int>> g;
    vector<int> dist1, dist2;
    priority_queue<PII, vector<PII>, greater<PII>> heap;

    int secondMinimum(int n, vector<vector<int>>& edges, int time, int change) {

        g.resize(n + 1);
        dist1 = dist2 = vector<int>(n + 1, 1e9);
        for (int i = 0; i < edges.size(); i++) {
            int a = edges[i][0], b = edges[i][1];
            g[a].push_back(b);
            g[b].push_back(a);
        }

        dist1[1] = 0;
        heap.push({0, 1});
        while (heap.size()) {
            auto t = heap.top();
            heap.pop();

            int u = t.y, distance = t.x;
            // cout << u << ' ' << dist1[u] << ' ' << dist2[u] << endl;

            // 计算动态边权
            int wait = 0;
            if ((distance / change) % 2 == 1) wait = change - distance % change;
            int d = distance + time + wait;  // 从u出发到达其他点用时
            for (auto v : g[u]) {
                if (d < dist1[v]) {
                    dist2[v] = dist1[v];
                    dist1[v] = d;
                    heap.push({dist1[v], v});
                    heap.push({dist2[v], v});
                } else if (d > dist1[v] && d < dist2[v]) {
                    dist2[v] = d;
                    heap.push({dist2[v], v});
                }
            }
        }

        return dist2[n];
    }
};

int main() {

    vector<vector<int>> edges = {{1, 2}, {1, 3}, {1, 4}, {3, 4}, {4, 5}};
    cout << Solution().secondMinimum(5, edges, 3, 5) << endl;  // 13

    return 0;
}
